বেসিক সর্টিং: Bubble Sort, Selection Sort, Insertion Sort

বেসিক সর্টিং অ্যালগরিদমগুলি হল প্রাথমিক এবং সহজ সর্টিং পদ্ধতি, যা ছোট ডেটাসেটের জন্য বেশ উপযোগী। এখানে Bubble Sort, Selection Sort, এবং Insertion Sort-এর কাজের পদ্ধতি এবং তাদের টাইম কমপ্লেক্সিটি নিয়ে আলোচনা করা হলো।

১. বাবল সর্ট (Bubble Sort)

Bubble Sort একটি সহজ সর্টিং অ্যালগরিদম, যেখানে তালিকার প্রতিটি উপাদান পর্যায়ক্রমে তুলনা করা হয় এবং প্রয়োজন অনুযায়ী তাদের বিনিময় করা হয়। এটি ধীরে ধীরে সবচেয়ে বড় উপাদানগুলিকে তালিকার শেষে নিয়ে যায়, ঠিক বুদবুদের মতো।

অ্যালগরিদমের প্রক্রিয়া:

1. প্রথম ইনডেক্স থেকে শুরু করে প্রতিটি উপাদান পরবর্তী উপাদানের সাথে তুলনা করা হয়।
2. যদি প্রথমটি পরেরটির চেয়ে বড় হয়, তাহলে তারা স্থান বিনিময় করে।
3. এই প্রক্রিয়াটি বারবার চলতে থাকে যতক্ষণ না তালিকার সমস্ত উপাদান সর্ট হয়ে যায়।

টাইম কমপ্লেক্সিটি:

• Best Case: O(n) (যদি তালিকাটি আগে থেকেই সর্টেড থাকে)
• Worst and Average Case: O(n^2)

উদাহরণ:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap
    return arr

২. সিলেকশন সর্ট (Selection Sort)

Selection Sort অ্যালগরিদমটি তালিকার প্রতিটি পজিশনে সবচেয়ে ছোট উপাদানটি খুঁজে এনে রাখে। এটি প্রথম পজিশনে সবচেয়ে ছোট উপাদানটি রাখে, তারপর দ্বিতীয় পজিশনে দ্বিতীয় ছোট উপাদান রাখে এবং এভাবে সর্টিং সম্পন্ন করে।

অ্যালগরিদমের প্রক্রিয়া:

1. প্রথমে সম্পূর্ণ তালিকা থেকে সবচেয়ে ছোট উপাদানটি খুঁজে বের করে প্রথম পজিশনে আনা হয়।
2. দ্বিতীয় পজিশনে পরবর্তী সবচেয়ে ছোট উপাদান খুঁজে এনে স্থাপন করা হয়।
3. এভাবে প্রতিটি পজিশনে যথাক্রমে ছোট উপাদানগুলি রাখে যতক্ষণ না তালিকাটি সর্ট হয়ে যায়।

টাইম কমপ্লেক্সিটি:

• Best, Worst, and Average Case: O(n^2) (এটি প্রতিটি ক্ষেত্রে একই থাকে)

উদাহরণ:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]  # Swap
    return arr

৩. ইনসার্শন সর্ট (Insertion Sort)

Insertion Sort তালিকার প্রতিটি উপাদানকে সঠিক পজিশনে ইনসার্ট করে সর্ট করে। এই অ্যালগরিদমটি প্রথমে একটি উপাদান নিয়ে তার স্থান নির্ধারণ করে এবং পরে পরবর্তী উপাদানগুলিকে ক্রমানুসারে তাদের সঠিক অবস্থানে ইনসার্ট করে সর্টিং সম্পন্ন করে।

অ্যালগরিদমের প্রক্রিয়া:

1. দ্বিতীয় উপাদান থেকে শুরু করে প্রতিটি উপাদানকে তার সঠিক স্থানে ইনসার্ট করা হয়।
2. ইনসার্ট করতে প্রথমে সঠিক পজিশন খুঁজে বের করা হয় এবং সেখানে উপাদানটিকে স্থাপন করা হয়।
3. এই প্রক্রিয়াটি তালিকার শেষ পর্যন্ত চালানো হয়।

টাইম কমপ্লেক্সিটি:

• Best Case: O(n) (যদি তালিকাটি আগে থেকেই সর্টেড থাকে)
• Worst and Average Case: O(n^2)

উদাহরণ:

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

তুলনা

এই তিনটি সর্টিং অ্যালগরিদম সাধারণত ছোট ডেটাসেট এবং শিক্ষণমূলক উদাহরণ হিসেবে ব্যবহৃত হয়। বড় ডেটাসেটের জন্য এগুলো কম কার্যকর, তাই বড় ডেটাসেটে Merge Sort বা Quick Sort এর মতো আরও কার্যকর অ্যালগরিদম ব্যবহৃত হয়।